package main

import (
	"fmt"
	. "local/algorithm/util"
	bst "local/datastructure/tree/binarySearchTree"
)

/**
1.递归
2.借助栈
*/

/*递归法
func inorderTraversal(root *TreeNode) []int {
	m := []int{}
	var helper func(root *TreeNode)
	helper = func(root *TreeNode) {
		if root == nil {
			return
		}
		helper(root.Left)
		m = append(m, root.Val)
		helper(root.Right)
	}

	helper(root)
	return m
}
*/

/*非递归 栈*/
func inorderTraversal(root *TreeNode) []int {
	list := []int{}
	stack := []*TreeNode{}
	cur := root
	for {
		if len(stack) == 0 || cur == nil {
			break
		}
		
		if cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		} else {
			cur = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			list = append(list, cur.Val)
			cur = cur.Right
		}
	}
	return list
}

func main() {
	t := bst.Generate([]int{2, 4, 5})
	fmt.Println(inorderTraversal(t))
}
